/*
==================================================================
* 版权所有 © 2025 CaryXiong
* Copyright (C) 2025 CaryXiong(a1816101108@outlook.com)
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
===================================================================
*/




#include<iostream>
using namespace std;

template<class DataType>
struct Node{
    DataType data;
    Node *next;
};

template<class DataType>
class LinkStack{
    public:
        LinkStack();
        LinkStack(DataType a[], int n);
        ~LinkStack();
        void Push(DataType x);
        DataType Pop();
        DataType GetTop();
        bool Empty();

        void PrintList();
        DataType Pop2();

    private:
        Node<DataType> *top;
        int length;
};

template<class DataType>
LinkStack<DataType> :: LinkStack(){
    top = nullptr;
    length = 0;
}

template<class DataType>
LinkStack<DataType> :: LinkStack(DataType a[], int n){
    top = new Node<DataType>;
    top->data = a[0];
    top->next = nullptr;

    // Node<DataType> *r;
    // r = top;
    for(int i=1; i<n; i++){
        Node<DataType> *s;
        s = new Node<DataType>;
        s->data = a[i];
        s->next = top;

        top = s;
    }
    length = n;
}

template<class DataType>
LinkStack<DataType> :: ~LinkStack(){
    Node<DataType> *s, *p=top;
    while(p != nullptr){
        s = p->next;
        delete p;
        p = s;
    }
}

template<class DataType>
void LinkStack<DataType> :: Push(DataType x){
    Node<DataType> *p;
    p = new Node<DataType>;

    p->data = x;
    p->next = top;
    top = p;
    length ++;
}

template<class DataType>
DataType LinkStack<DataType> :: Pop(){
    DataType value;
    Node<DataType> *p;
    value = top->data;

    p = top;
    top = top->next;
    delete p;
    length --;
    return value;
}

template<class DataType>
DataType LinkStack<DataType> :: GetTop(){
    return top->data;
}

template<class DataType>
bool LinkStack<DataType> :: Empty(){
    if(top == nullptr) return true;
    else return false;
}




template<class DataType>
void LinkStack<DataType> :: PrintList(){
    Node<DataType> *p = top;
    if(Empty()) throw "表空 无法打印表";

    while(p != nullptr){
        cout << p->data << '\t';
        p = p->next;
    }
    cout << '\n';
}

template<class DataType>
DataType LinkStack<DataType> :: Pop2(){
    Node<DataType> *p=top, *s;
    DataType value;
    if(Empty()) throw "表空无法Pop";
    if(length > 1){
        value = top->data;
        s = top->next->next;
        delete p->next;
        delete p;
        top = s;
        length = length-2;
        return value;
    }
    if(length == 1){
        value = top->data;
        delete top;
        top = nullptr;
        length = 0;
        return value;
    }
    return -1;
}


int main(){
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    LinkStack<int> S1(a,10);
    
    cout << "当前链栈内容为：";
    S1.PrintList();

    S1.Push(100);
    cout << "Push元素100到栈顶，当前链栈内容为：";
    S1.PrintList();

    cout << "弹出栈顶元素：" << S1.Pop() << endl;
    cout << "当前链栈内容为：";
    S1.PrintList();

    cout << "获取栈顶元素：" << S1.GetTop() << endl;

    cout << "判断该链栈是否为空：";
    if(S1.Empty()) cout << "空" << endl;
    else cout << "非空" << endl;

    cout << "弹出两个栈顶元素，返回原栈顶数据：" << S1.Pop2() << endl;
    cout << "当前链栈内容为：";
    S1.PrintList();

    cout << endl << endl << endl;

    LinkStack<int> S2;
    S2.Push(3);
    cout << "测试链栈中只有一个元素时，Pop2函数的运行结果：" << endl;
    cout << "只弹出栈顶的元素：" << S2.Pop2() << endl;

    cout << "判断该链栈是否为空：";
    if(S2.Empty()) cout << "空" << endl;
    else cout << "非空" << endl;

    int m;
    cin >> m;
}